import org.junit.Test;

import java.util.Arrays;

public class Solution5 {
    /**
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     */
    // 暴力
    public String longestPalindrome(String s) {
        if (s.equals("")) return "";
        char[] chars = new char[s.length() * 2 - 1];
        int max = 0;
        int idx = 0;
        Arrays.fill(chars, '*');
        for (int i = 0; i < s.length(); i++) {
            chars[i * 2] = s.charAt(i);
        }
        for (int i = 0; i < chars.length; i++) {
            int width = 0;
            while (i - width >= 0 && i + width < chars.length && chars[i - width] == chars[i + width]) {
                width++;
            }
            if (chars[i + width - 1] == '*') width--;
            if (width - 1 > max) {
                max = width - 1;
                idx = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = idx - max; i <= idx + max; i += 2) {
            if (chars[i] == '*') i++;
            sb.append(chars[i]);
        }
        return sb.toString();
    }

    @Test
    public void test() {
        longestPalindrome2("cbbd");
    }


    // 马拉车

    public String preHandleString(String s) {
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        sb.append('#');
        for (int i = 0; i < len; i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }

    public String longestPalindrome2(String s) {
        String str = preHandleString(s);
        int len = str.length();
        int right = 0;
        int rightMid = 0;
        int[] widths = new int[len];
        int max = 0;
        int idx = 0;
        for (int i = 0; i < len; i++) {
            boolean needCalc = true;
            if (right >= i) {
                widths[i] = widths[2 * rightMid - i];
                if (i + widths[i] >= right) {
                    widths[i] = right - i;
                } else {
                    needCalc = false;
                }
            }
            if (needCalc) {
                while (i - widths[i] - 1 >= 0 && i + widths[i] + 1 < len && str.charAt(i + widths[i] + 1) == str.charAt(i - widths[i] - 1)) {
                    widths[i]++;
                }
                right = i + widths[i];
                rightMid = i;
                if (widths[i] > max) {
                    idx = i;
                    max = widths[i];
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = idx - max + 1; i <= idx + max; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();

    }
}
